package questionSolution.Question_1;

import java.util.HashMap;
import java.util.Scanner;

/*
可以使用哈希表优化解法，通过空间换时间将时间复杂度降至O(n)。
核心思路是：遍历数组时，用目标值减去当前元素得到“补救”，若补数已在哈希表中，则直接这道对应的两个索引；
         若不在，则将当前元素及其索引存入哈希表
ps:一定要先计算temp，再进行map.put(nums[i], i)，否则可能会匹配到自身

 */
public class Solution_2 {
    public int[] twoSum(int[] nums, int target){
        int [] res = new int[2];
        HashMap<Integer,Integer> map = new HashMap<Integer,Integer>();
        for(int i = 0; i < nums.length; i++){
            int temp = target - nums[i];
            if(map.containsKey(temp)){
                res[0] = map.get(temp);
                res[1] = i;
            }
            map.put(nums[i], i);
        }
        return res;
    }

    static void main() {
        Solution_2 s = new Solution_2();
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] arr = new int[n];
        int[] res = new int[n];
        for(int arr_i = 0; arr_i < n; arr_i++){
            arr[arr_i] = sc.nextInt();
        }
        int target = sc.nextInt();
        res = s.twoSum(arr, target);
        System.out.println(res[0] + " " + res[1]);
    }

}
